package edu.bupt.e1btree;

public class T46PopulatingNextRightPointers {
    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val,Node _left,Node _right,Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }

    public Node connect(Node root) {
        dfs(root);
        return root;
    }

    private void dfs(Node root){
        //终止条件/收敛条件
        if (null == root) return;

        //状态表示
        little(root.left, root.right);
        //扩展
        if (null != root.left){
            dfs(root.left);
        }
        if (null != root.right){
            dfs(root.right);
        }

    }

    private void little(Node left, Node right){
        while (null != left){
            left.next = right;
            left = left.right;
            right = right.left;
        }
    }

}
